'''
有序字典
'''
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        leftres = []
        rightres = []
        self.head = None
        def midorder(root,res):
            if root==None:
                return
            midorder(root.left,res)
            res.append(root)
            midorder(root.right,res)
        midorder(root.left,leftres)
        midorder(root.right,rightres)
        self.head = leftres[0]
        for i in range(len(leftres)-1):
            if i == 0:
                self.head.right = leftres[i+1]
                leftres[i+1].left = self.head
            else:
                leftres[i].right = leftres[i+1]
                leftres[i+1].left = leftres[i]
        leftres[-1].right = root
        root.left = leftres[-1]
        for i in range(len(rightres)-1):
            rightres[i].right = rightres[i+1]
            rightres[i+1].left = rightres[i]
        self.head.left = rightres[-1]
        rightres[-1].right = self.head
        return self.head
if __name__ == '__main__':
    root = Node(4)
    root.left = Node(2)
    root.right = Node(5)
    root.left.left = Node(1)
    root.left.right = Node(3)
    s = Solution()
    r = s.treeToDoublyList(root)
    print(r.val)
    print(r.right.val)
    print(r.right.right.val)
    print(r.right.right.right.val)
    print(r.right.right.right.right.val)
    print(r.right.right.right.right.right.val)
    print(r.left.val)


